home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / array.tex next >
Encoding:
Text File  |  1994-08-05  |  3.5 KB  |  88 lines
  1. {\magonebf 3.1 One Dimensional Arrays (array)}
  2.  
  3. \decl array E 
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $A$ of the parameterized data type \name\ is a mapping from 
  8. an interval $I =[a..b]$ of integers, called the index set of $A$, to the set of 
  9. variables of data type $E$, called the element type of $A$. $A(i)$ 
  10. is called the element at position $i$. 
  11.  
  12.  
  13. \bigskip
  14. {\bf 2. Creation}
  15.  
  16. \create A (int\ a,\ int\ b)
  17.  
  18. creates an instance \var\ of type \name\ with index set $[a..b]$.
  19.  
  20.  
  21. \bigskip
  22. {\bf 3. Operations}
  23. \cleartabs
  24. \+&\hskip 1.5truecm &\hskip 6truecm &\cr
  25. \+\opa E\&   {int\ i}                     
  26.                                      {returns $A(i)$. \precond $a\le i\le b$  }
  27. \smallskip
  28. \+\op  int   low {}                  
  29.                                      {returns the minimal index $a$}
  30. \smallskip
  31. \+\op  int   high {}                 
  32.                                      {returns the maximal index $b$}
  33. \smallskip
  34. \+\op  void  sort {int\ (*cmp)(E\&, E\&)} 
  35.                      {sorts the elements of \var, using function $cmp$}
  36. \+\nop               {to compare two elements, i.e., if $(in_a,\dots,in_b)$}
  37. \+\nop               {and $(out_a,\dots,out_b)$ denote the values of the}
  38. \+\nop               {variables $(A(a),\dots,A(b))$ before and after the}
  39. \+\nop               {call of sort, then $cmp(out_i,out_j) \le 0$ for $i\le j$}
  40. \+\nop               {and there is a permutation $\pi$ of $[a..b]$ such that}
  41. \+\nop               {$out_i=in_{\pi(i)}$ for $a \le i \le b$.}
  42. \smallskip
  43. \+\op  void  sort {int\ (*cmp)(E\&, E\&),\ int\ l,\ int\ h}  {}
  44. \+\nop               {applies the above defined sorting operations to}
  45. \+\nop               {the sub-array \var$[l..h]$.}
  46. \smallskip
  47. \+\op  int   binary\_search {E\ x,\ int\ (*cmp)(E\&, E\&)}  {}
  48. \+\nop               {performs a binary search for $x$. Returns $i$}
  49. \+\nop               {with $A[i] = x$ if $x$ in $A$, $A$.low$()-1$}
  50. \+\nop               {otherwise. Function $cmp$ is used to compare}
  51. \+\nop               {two elements. \precond $A$ must be sorted}
  52. \+\nop               {according to $cmp$.}
  53. \medskip
  54. \+\op void       read {istream\ I}
  55.                      {reads $b-a+1$ objects of type $E$ from the}
  56. \+\nop               {input stream $I$ into the array $A$ using the}
  57. \+\nop               {overloaded $Read$ function (cf.~section 1.5)}
  58. \smallskip
  59. \+\op void       read {}
  60.                      {Calls $A$.read($cin$) to read $A$ from the}
  61. \+\nop               {standard input stream $cin$.}
  62. \smallskip
  63. \+\op void       read {string\ s}
  64.                      {As above, uses string $s$ as a prompt.}
  65. \medskip
  66. \+\op void       print {ostream\ O,\ char\ space =\ '\ '}    {} 
  67. \+\nop               {Prints the contents of array $A$ to the output}
  68. \+\nop               {stream $O$ using the overload $Print$ function}
  69. \+\nop               {(cf.~section 1.5) to print each element. The}
  70. \+\nop               {elements are separated by the character $space$.}
  71. \smallskip
  72. \+\op void       print {char\ space =\ '\ '}
  73.                      {Calls $A$.print($cout$, $space$) to print $A$ on}
  74. \+\nop               {the standard output stream $cout$.}
  75. \smallskip
  76. \+\op void       print {string\ s,\ char\ space =\ '\ '}    {} 
  77. \+\nop               {As above, uses string $s$ as a header.}
  78.  
  79.  
  80. \bigskip
  81. {\bf 4. Implementation}
  82.  
  83. Arrays are implemented by \CC vectors. The access operation takes time
  84. $O(1)$, the sorting is realized by quicksort (time $O(n \log n)$) and
  85. the binary\_search operation takes time $O(\log n)$, where $n = b-a+1$.
  86. The space requirement is $O(|I|)$.
  87.  
  88.